Damerau-Levenshtein 거리
Damerau-Levenshtein 거리
개요
amerau-Levenshtein 거리(Damerau-Levenshtein Distance)는 두 문자열 간의 유사도를 측정하는 편집 거리(Edit Distance)의 일종으로, 문자열을 서로 변환하기 위해 필요한 최소 편집 연산의 수를 계산한다. 이 거리는 러시아 수학자 블라디미르 레벤슈타인(Vladimir Levenshtein)이 제안한 레벤슈타인 거리(Levenshtein Distance)를 확장한 개념이며, 미국의 컴퓨터 과학자 프레드릭 더머(Frederick J. Damerau)가 인접한 문자의 치환(transposition) 연산을 추가하여 보완하였다.
Damerau-Levenshtein 거리는 철자 교정(Spell checking), 자연어 처리(NLP), 생물정보학(Bioinformatics), 문자열 매칭 등 다양한 분야에서 널리 활용된다. 특히, 인간의 입력 오류 중 흔히 발생하는 "문자 순서 바꾸기" 현상(예: "hte" → "the")을 효과적으로 처리할 수 있어, 일반적인 레벤슈타인 거리보다 실용성이 높다.
기본 개념
정의
Damerau-Levenshtein 거리는 두 문자열을 동일하게 만들기 위해 필요한 최소 편집 연산의 횟수를 나타내며, 허용되는 연산은 다음과 같다:
- 삽입(Insertion): 한 문자를 문자열에 추가
- 삭제(Deletion): 한 문자를 문자열에서 제거
- 치환(Substitution): 한 문자를 다른 문자로 변경
- 전치(Transposition): 인접한 두 문자의 위치를 서로 바꿈
예를 들어, 문자열 "cafe"와 "face" 사이의 거리는 다음과 같이 계산할 수 있다:
- 'c'와 'f'를 전치 → "fcae"
- 'c'와 'a'를 전치 → "faec"
- 'e'와 'c'를 전치 → "face"
하지만 더 효율적인 경로는:
- 'c'를 삭제하고 마지막에 추가 → "afe" → "afec" → "face" (3회 연산)
실제 최적 경로는 동적 프로그래밍을 통해 구할 수 있으며, 이 경우 전치 연산을 한 번 사용하면 "cafe" → "face"를 2회 연산(전치 + 전치)으로 변환할 수 있다.
알고리즘 구현
Damerau-Levenshtein 거리는 동적 프로그래밍을 기반으로 구현된다. 문자열 A와 B의 길이를 각각 m과 n이라 할 때, (m+1) × (n+1) 크기의 2차원 배열 dp를 사용한다.
재귀적 정의
dp[i][j]는 A의 첫 i개 문자와 B의 첫 j개 문자 사이의 Damerau-Levenshtein 거리를 나타낸다.
def damerau_levenshtein(a, b):
m, n = len(a), len(b)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
cost = 0 if a[i-1] == b[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # 삭제
dp[i][j-1] + 1, # 삽입
dp[i-1][j-1] + cost # 치환
)
if i > 1 and j > 1 and a[i-1] == b[j-2] and a[i-2] == b[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) # 전치
return dp[m][n]
⚠️ 위 구현은 간단한 버전으로, 인접한 두 문자의 전치만을 고려한다. 복잡한 전치(예: 삽입 후 전치 등)를 처리하려면 더 정교한 알고리즘이 필요하다.
활용 분야
자연어 처리(NLP)
- 철자 교정: 사용자 입력에서 흔히 발생하는 오타(예: "hte", "adn")를 인식하고 정정
- 음성 인식 후처리: 발음 유사성에 기반한 오류 수정
- 의사 결정 시스템: 유사한 질문이나 명령어 인식에 활용
생물정보학
정보 검색
특징 및 한계
장점
- 전치 연산을 포함하여 인간의 입력 오류를 더 잘 모델링
- 레벤슈타인 거리보다 실세계 텍스트 오류에 강건함
- 비교적 간단한 알고리즘 구조
한계
- 전치 연산이 인접한 두 문자에만 적용 가능 (일반적인 전치는 처리 불가)
- 시간 및 공간 복잡도:
O(m×n)→ 긴 문자열 처리에 비효율적 - 비인접 전치나 복잡한 오타 패턴은 포착 어려움
관련 개념
| 개념 | 설명 |
|---|---|
| Levenshtein Distance | 삽입, 삭제, 치환만 허용 |
| Hamming Distance | 같은 길이 문자열에서 서로 다른 위치의 수 |
| Jaro-Winkler Distance | 전치를 고려한 문자열 유사도 측정, 이름 매칭에 적합 |
| Optimal String Alignment Distance | 제한된 전치만 허용하는 Damerau-Levenshtein의 단순화된 버전 |
참고 자료
- Damerau, F. J. (1964). "A technique for computer detection and correction of spelling errors". Communications of the ACM.
- Levenshtein, V. I. (1966). "Binary codes capable of correcting deletions, insertions, and reversals". Soviet Physics Doklady.
- Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
📚 추가 학습: 문자열 알고리즘, 동적 프로그래밍, 편집 거리 변형 알고리즘 (예: Ukkonen's algorithm)
이 문서는 AI 모델(qwen-3-235b-a22b-instruct-2507)에 의해 생성된 콘텐츠입니다.
주의사항: AI가 생성한 내용은 부정확하거나 편향된 정보를 포함할 수 있습니다. 중요한 결정을 내리기 전에 반드시 신뢰할 수 있는 출처를 통해 정보를 확인하시기 바랍니다.